package com.zp.self.module.level_4_算法练习.数据结构.二叉树;

/**
 * @author By ZengPeng
 */
public class 力扣_96_不同的二叉搜索树 {
    //测试
    public static void main(String[] args) {
        System.out.println(new 力扣_96_不同的二叉搜索树().numTrees(1));
        System.out.println(new 力扣_96_不同的二叉搜索树().numTrees(2));
        System.out.println(new 力扣_96_不同的二叉搜索树().numTrees(3));
        System.out.println(new 力扣_96_不同的二叉搜索树().numTrees(4));
        System.out.println(new 力扣_96_不同的二叉搜索树().numTrees(5));
        System.out.println(new 力扣_96_不同的二叉搜索树().numTrees(6));
        System.out.println(new 力扣_96_不同的二叉搜索树().numTrees(7));
        System.out.println(new 力扣_96_不同的二叉搜索树().numTrees(8));
        System.out.println(new 力扣_96_不同的二叉搜索树().numTrees(19));
    }

    /**
    题目：给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

     示例 1：
     输入：n = 3
     输出：5

     示例 2：
     输入：n = 1
     输出：1

    分析：【P 💜💜💜💜】
       1.回溯法？尾递归？：遍历1->n  让每个节点都做头节点，
                           小于head 的放在右边，大于head 的放在右边
                            每次区间传入的start,end 相差1、2 则返回1，2中，其它的继续递归
            --执行用时：1513 ms, 在所有 Java 提交中击败了5.71%的用户
       2.动态规划：递归时加个结果缓存数组 --即：带备忘录的递归
            --执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

    边界值 & 注意点：
       1.java 中需要重新重建对象，而不是只改动左右指针，这样会导致加入集合的始终是那一个对象
     **/
    public int numTrees(int n) {
        int[] dp =new int[n+1];
        dp[0]=1;
        dp[1]=1;
        dfs(n,dp);
        return dp[n];
    }

    private int dfs(int n,int[] dp) {
        if(dp[n]!=0) return dp[n];
        int sum=0;
        for (int i = 1; i <= n; i++) {//用谁做头节点
            sum+=(dfs(i - 1,dp) * dfs(n - i,dp));
        }
        dp[n]=sum;
        return dp[n];
    }

    // 1.回溯法？尾递归？：遍历1->n  让每个节点都做头节点，
   /* private int dfs(int start, int end) {
        if(start>end) return 0;
        int numbs = end - start+1;
        if(numbs==1 || numbs==2) return numbs;
        int sum =0;
        for (int i = start; i <= end; i++) {
            int left=  dfs(start,i-1);
            int right=  dfs(i+1,end);
            if(left==0){
                sum+=right;
            }else if(right==0){
                sum+=left;
            }else {
                sum+=(left*right);
            }
        }
        return sum;
    }*/
}
